package com.zk.algorithm.dynamicprogramming;

import com.zk.algorithm.annotation.Easy;
import com.zk.algorithm.annotation.LeetCodeExplore;

import java.util.Arrays;

/**
 * Each house has a certain amount of money stashed,
 * the only constraint stopping you from robbing each of them is that adjacent houses
 * have security system connected and it will automatically contact the police
 * if two adjacent houses were broken into on the same night.
 *
 * 相邻的不能偷
 *
 * 下面的这个链接对于常见的 DP 问题的分析方法，讲的很透彻
 * https://leetcode.com/explore/interview/card/top-interview-questions-easy/97/dynamic-programming/576/discuss/156523/From-good-to-great.-How-to-approach-most-of-DP-problems.
 *
 * @author zk
 */
@LeetCodeExplore
@Easy
public class HouseRobber {

    // 一、recursive
    //  - 偷当前 i: 不能偷 i - 1，可以偷 i - 2
    //  - 不偷当前: 可以偷 i - 1
    //
    // rob(i) = Math.max(rob(i - 2) + currentHouseValue, rob(i - 1))
    // 代码如下，需要优化
    //
    // recursive + memo

    int[] memo;

    public int rob(int[] nums) {
        memo = new int[nums.length + 1];
        Arrays.fill(memo, -1);

        return rob(nums, nums.length - 1);
    }

    private int rob(int[] nums, int i) {
        if (i < 0) {
            return 0;
        }

        if (memo[i] >= 0) {
            return memo[i];
        }

        int result = Math.max(rob(nums, i - 2) + nums[i], rob(nums, i - 1));
        memo[i] = result;
        return result;
    }

}